1. Field of the Invention
The present invention relates generally to a method of error correction, and in particular is directed to a method of error correction by which an error correcting code (a kind of adjacent code) capable of correcting up to two word errors in one block is used to correct errors at high speed.
2. Description of the Prior Art
There has been previously proposed, for example, in copending application Ser. No. 218,256, filed Dec. 19, 1980, now U.S. Pat. No. 4,355,392 issued Oct. 19, 1982, and having a common assignee herewith, a data transmission system effective for correcting burst errors using a so-called cross-interleave technique. In such cross-interleave technique, words in a PCM (pulse code modulated) data signal series are provided in plural sequences on plural respective channels arranged in a first arrangement state, and are furnished to a first error-correcting coder to generate therefrom a first check word series. This first check word series and the PCM data signal series in the plural channels are converted to a second arrangement state. Then, one word in the second arrangement state for each of the PCM data signal sequences in the plural channels is furnished to a second error correcting coder to generate therefrom a second check word series, so that a double interleave (i.e., double rearrangement) is carried out for each word. The purpose of the double interleave is to reduce the number of erroneous words in any group of words contained in a common error-correcting block when the check word contained in such erro-correcting block and the PCM data associated therewith are dispersed and transmitted. Any such erroneous words are dispersed among several blocks, and are returned to the original arrangement thereof at the receiving side. In other words, when a burst error develops during transmission, the burst error can be dispersed. If the above interleave is performed twice, the first and second check words each are used to correct words in distinct error correcting blocks. Thus, even if an error cannot be corrected by one of the first and second check words, the error can be corrected by the other check word. Therefore, this technique provides a significant advance in error correcting ability for burst errors.
However, when even one bit in one word is discovered to be in error, the entire word is considered erroneous. Therefore, when a received data signal has a relatively large number of random errors, the above-described double interleave technique is not always sufficiently powerful for correcting these random errors.
To this end, it is proposed that an error correcting code high in error correcting ability, for example, Reed-Solomon (RS) Code, Bose-Chaudhuri-Hocquenghem (BCH) code, or a variant of a b-adjacent code, which can corred K word errors, for example, two word errors in one block, and can also correct M word errors, for example, three word errors or four word errors, if the location of errors is known, is combined with the above multi-interleave technique.
This error correcting code enables the simplification of the construction of a decoder when only one word error is to be corrected.
However, when two word errors are to be corrected, since the fundamental algorithm of error correction is such that by using the syndrome it is checked in the first step whether or not there is an error, it is checked in the second step whether or not the error is one word error and it is checked in the third step whether or not the error is two word errors, the time period required to complete all the steps becomes rather long. This problem will appear especially troublesome when the error locations of two word errors are calculated.